package meet;

/**
 * @author ：szq
 * @date ：Created in 2022/3/21 15:45
 * @description：Tarjan算法是基于对图深度优先搜索的算法，
 * 每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，
 * 回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
 * @modified By：
 * @version: $
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;


public class Tarjan {
    private int numOfNode;
    private List< ArrayList<Integer>> graph;//图
    private List< ArrayList<Integer>> result;//保存极大强连通图
    private boolean[] inStack;//节点是否在栈内，因为在stack中寻找一个节点不方便。这种方式查找快
    private Stack<Integer> stack;
    private int[] dfn;
    private int[] low;
    private int time;//

    public Tarjan(List< ArrayList<Integer> > graph,int numOfNode){ //初始化图表 和辅助数组
        this.graph = graph;
        this.numOfNode = numOfNode;
        this.inStack = new boolean[numOfNode];
        this.stack = new Stack<Integer>();
        dfn = new int[numOfNode];
        low = new int[numOfNode];
        Arrays.fill(dfn, -1);//将dfn所有元素都置为-1，其中dfn[i]=-1代表i还有没被访问过。
        Arrays.fill(low, -1);
        result = new ArrayList<ArrayList<Integer>>();
    }

    public List< ArrayList<Integer> > run(){
        for(int i=0;i<numOfNode;i++){//访问每个节点的邻节点
            if(dfn[i]==-1){
                tarjan(i);
            }
        }
        return result;
    }

    public void tarjan(int current){
        dfn[current]=low[current]=time++;// 第一次遍历的序号
        inStack[current]=true; //在栈里
        stack.push(current);//进栈

        for(int i=0;i<graph.get(current).size();i++){//访问当前邻接点的节点//
            int next = graph.get(current).get(i);//
            if(dfn[next]==-1){//-1代表没有被访问
                tarjan(next);
                low[current]=Math.min(low[current], low[next]);
            }else if(inStack[next]){
                low[current]=Math.min(low[current], dfn[next]);
            }
        }

        if(low[current]==dfn[current]){ //只要不是追溯到它本身 都不是联通的。
            //？回不回存在这么 进栈的有交叉。实验证明 不会存在两个交叉的联通图
            ArrayList<Integer> temp =new ArrayList<Integer>();
            int j = -1;
            while(current!=j){
                j = stack.pop();
                inStack[j]=false;
                temp.add(j);
            }
            result.add(temp);
        }
    }

}
